using System;
using System.Collections;
using System.Threading;

public class SudokuI16
{
    static Random rand = new Random();
    static ulong MASK;
    static int N, N2, N3, N4, N6, N2_1, N2_2, N4_1, qn, hi;
    static bool done;


    static int[,] tb;
    static int[, ,] tb3;
    static int[] h1, h2, h3;
    static int[] rs;
    static Set[] sets;
    static Cell[] cells;
    static int[][] subs, pairs, pairsOfSubs;
    static ulong[] subsMask, pairsMask;
    static IQ subsIQ, pairsIQ, setsIQ;
    public int[] queryResults(int x, int[] qr)
    {
        cells[(qr[0] - 1) * N2 + qr[1] - 1].mask(1LU << (x - 1));
        if (qn < N2)
        {
            qr[1] = N * (qn % N) + (qn / N) + 1;
            qr[0] = ++qn;
            return qr;
        }
        double best = double.MinValue, tt;
        int bestk = -1, k;
    Loop:
        while ((k = setsIQ.Next()) >= 0)
            sets[k].check();
        done = false;
        while ((k = subsIQ.Next()) >= 0)
        {
            ulong m = 0LU;
            foreach (int mid in subs[k])
                m |= cells[mid].mk;
            if (subsMask[k] != m)
            {
                subsMask[k] = m;
                foreach (int pid in pairsOfSubs[k])
                    pairsIQ.Add(pid);
            }
        }
        while ((k = pairsIQ.Next()) >= 0)
        {
            ulong m = 0LU;
            foreach (int sid in pairs[k])
                m |= subsMask[sid];
            if (pairsMask[k] != m)
            {
                pairsMask[k] = m;
                pairsMask[k ^ 1] = m;
                foreach (int sid in pairs[k ^ 1])
                    foreach (int mid in subs[sid])
                        if (rs[mid] == 0)
                            cells[mid].mask(m);
            }
        }
        if (done)
            goto Loop;

        for (k = N4_1; k >= 0; k--)
            if (rs[k] == 0 && (tt = cells[k].value) >= best)
            {
                best = tt; bestk = k;
            }
        if (bestk >= 0)
            return new int[] { (bestk / N2) + 1, (bestk % N2) + 1 };
        return rs;
    }

    public int[] initialize(int n)
    {
        int i, j, k, l, s, e, a, b;
        qn = 1;
        N = n;
        N2 = n * n;
        N3 = N2 * n;
        N4 = N3 * n;
        N6 = N3 * N3;
        N2_1 = N2 - 1;
        N2_2 = N2 - 2;
        N4_1 = N4 - 1;
        MASK = 1LU << (N2_1);
        MASK = (MASK - 1) + MASK;

        rs = new int[N4];
        cells = new Cell[N4];
        for (i = N4_1; i >= 0; i--)
            cells[i] = new Cell(i);

        tb = new int[N2, N2];
        for (i = N2_1; i >= 0; i--)
            for (j = N2_1; j >= 0; j--)
                tb[i, j] = -1;
        tb3 = new int[N2, N2, N2];

        h1 = new int[N4];
        h2 = new int[N4];
        h3 = new int[N4];


        subsIQ = new IQ(2 * N3);
        pairsIQ = new IQ(4 * N3);
        setsIQ = new IQ(3 * N2);

        subs = new int[2 * N3][];
        subsMask = new ulong[2 * N3];
        pairsOfSubs = new int[2 * N3][];
        for (i = subs.Length - 1; i >= 0; i--)
        {
            subs[i] = new int[n];
            subsMask[i] = MASK;
            pairsOfSubs[i] = new int[2 * (n - 1)];
        }
        pairs = new int[4 * N3][];
        pairsMask = new ulong[4 * N3];
        for (i = pairs.Length - 1; i >= 0; i--)
        {
            pairs[i] = new int[n - 1];
            pairsMask[i] = MASK;
        }

        sets = new Set[3 * N2];
        for (i = sets.Length - 1; i >= 0; i--)
            sets[i] = new Set(i);
        for (k = N4_1; k >= 0; k--)
        {
            i = k / N2;
            j = k % N2;
            sets[i].list[j] = cells[k].r;
            sets[N2 + j].list[i] = cells[k].c;
            sets[N2 + N2 + i / n * n + j / n].list[(i % n) * n + (j % n)] = cells[k].a;
            cells[k].s1 = a = i * n + j / n;
            cells[k].s2 = b = N3 + j * n + i / n;
            subs[a][j % n] = k;
            subs[b][i % n] = k;
        }
        for (i = sets.Length - 1; i >= 0; i--)
            sets[i].init();

        int d = N3 << 1;
        int[] posp = new int[pairsOfSubs.Length];
        for (k = N3 - 1; k >= 0; k--)
        {
            i = k / n;
            j = k % n;
            a = k << 1;
            for (l = 0, s = i * n, e = s + n; s < e; s++)
                if (s != k)
                {
                    pairs[a][l] = s;
                    pairs[d + a][l] = b = N3 + s;
                    l++;
                    pairsOfSubs[s][posp[s]++] = a;
                    pairsOfSubs[b][posp[b]++] = d + a;
                }
            a++;
            for (l = 0, s = i / n * N2 + j, e = s + N2; s < e; s += n)
                if (s != k)
                {
                    pairs[a][l] = s;
                    pairs[d + a][l] = b = N3 + s;
                    l++;
                    pairsOfSubs[s][posp[s]++] = a;
                    pairsOfSubs[b][posp[b]++] = d + a;
                }
        }
        return new int[] { 1, 1 };
    }

    static int Count(ulong m)
    {
        int ret = 0;
        while (m > 0)
        {
            ret++;
            m = (m - 1) & m;
        }
        return ret;
    }
    static int First(ulong m)
    {
        for (int q = 0; q < N2; q++)
            if ((m & (1LU << q)) != 0LU)
                return q;
        if (m == 0)
            throw new Exception();
        return -1;
    }

    class Cell
    {
        public Cell(int k)
        {
            this.k = k;
            this.mk = MASK;
            this.r = new Element(this);
            this.c = new Element(this);
            this.a = new Element(this);
        }
        public ulong mk;
        public int s1, s2, k;
        public Element r, c, a;
        public override string ToString()
        {
            return k.ToString() + " " + mk.ToString("X16");
        }
        public void get(int x)
        {
            mk = 1LU << x;
            subsIQ.Add(s1);
            subsIQ.Add(s2);
            r.update(mk);
            c.update(mk);
            a.update(mk);
            rs[k] = x + 1;
            r.get(x);
            c.get(x);
            a.get(x);
        }
        public bool mask(ulong m)
        {
            if (mk != (mk & m))
            {
                mk &= m;
                subsIQ.Add(s1);
                subsIQ.Add(s2);
                r.update(mk);
                c.update(mk);
                a.update(mk);
                if (((mk - 1) & mk) == 0)
                {
                    int x = First(mk);
                    rs[k] = x + 1;
                    r.get(x);
                    c.get(x);
                    a.get(x);
                }
                done = true;
                return true;
            }
            return false;
        }
        public double value
        {
            get
            {
                return 3 * N * Count(mk) + (k / N2) + (k % N2) + rand.NextDouble();
            }
        }
    }
    class Element
    {
        public Element(Cell c)
        {
            cell = c;
            mk = MASK;
        }
        public Element left, right;
        public Set owner;
        public Cell cell;
        public ulong mk;
        public ulong pmk;
        public int eid;
        public void update(ulong m)
        {
            mk = m;
            setsIQ.Add(owner.sid);
            m ^= MASK;
            for (int i = 0; m != 0; m >>= 1, i++)
            {
                if ((m & 1LU) != 0)
                    owner.ps[i] &= pmk;
                //else
                //    owner.ps[i] |= ~pmk;
            }
        }
        public void get(int x)
        {
            owner.mk ^= 1LU << x;
            owner.ps[x] = 0LU;
            owner.size--;
            left.right = right;
            right.left = left;
        }
        public override string ToString()
        {
            return "[" + eid + "]" + base.ToString();
        }
    }
    class Set
    {
        public Set(int sid)
        {
            this.sid = sid;
            this.size = N2;
            this.head = new Element(null);
            this.list = new Element[N2];
            mk = MASK;
            ps = new ulong[N2];
            for (int i = N2_1; i >= 0; i--)
                ps[i] = MASK;
        }
        public int sid, size;
        public ulong[] ps;
        bool changed;
        public ulong mk, mkb;
        public Element head;
        public Element[] list;
        public void init()
        {
            head.right = list[0];
            list[0].owner = this;
            list[0].eid = 0;
            list[0].pmk = 1LU ^ MASK;
            list[0].left = head;
            list[0].right = list[1];
            for (int i = N2 - 2; i > 0; i--)
            {
                list[i].owner = this;
                list[i].eid = i;
                list[i].pmk = (1LU << i) ^ MASK;
                list[i].left = list[i - 1];
                list[i].right = list[i + 1];
            }
            list[N2_1].owner = this;
            list[N2_1].eid = N2_1;
            list[N2_1].pmk = (1LU << N2_1) ^ MASK;
            list[N2_1].left = list[N2 - 2];
            list[N2_1].right = head;
            head.left = list[N2_1];
        }
        public void check()
        {
            setsIQ.m[sid] = -1;
            int i;
        Loop:
            changed = false;
            #region 1i
            Element e = head.right, ee;
            mkb = mk;
            while (e != head)
            {
                e.cell.mask(mk);
                if (mk != mkb)
                {
                    mkb = mk;
                    e = head.right;
                }
                else
                    e = e.right;
            }
            #endregion;
            #region 1x
            ulong m;
            for (i = N2_1; i >= 0; i--)
                if (ps[i] != 0)
                {
                    m = ps[i];
                    if (((m - 1) & m) == 0)
                    {
                        list[First(m)].cell.get(i);
                        goto Loop;
                    }
                }
            #endregion

            #region 2i
            int a1, a2, a;
            hi = 0;
            for (e = head.right; e != head; e = e.right)
            {
                m = (e.mk - 1) & e.mk;
                if (m == 0)
                    throw new Exception();
                if (((m - 1) & m) == 0)
                {
                    a1 = First(e.mk);
                    a2 = First(m);
                    if ((a = tb[a1, a2]) > 0)
                    {
                        m = e.mk ^ MASK;
                        for (ee = head.right; ee.eid != a; ee = ee.right)
                        {
                            changed |= ee.cell.mask(m);
                            if (mk != mkb)
                                goto Clear2i;
                        }
                        for (ee = ee.right; ee != e; ee = ee.right)
                        {
                            changed |= ee.cell.mask(m);
                            if (mk != mkb)
                                goto Clear2i;
                        }
                        for (ee = ee.right; ee != head; ee = ee.right)
                        {
                            changed |= ee.cell.mask(m);
                            if (mk != mkb)
                                goto Clear2i;
                        }
                    }
                    else
                    {
                        tb[a1, a2] = e.eid;
                        h1[hi] = a1;
                        h2[hi] = a2;
                        hi++;
                    }
                }
            }
        Clear2i:
            while (--hi >= 0)
                tb[h1[hi], h2[hi]] = -1;
            if (changed)
                goto Loop;
            #endregion
            #region 2x
            ulong mm;
            hi = 0;
            for (i = 0; i < N2; i++)
                if (ps[i] != 0)
                {
                    m = ps[i];
                    mm = (m - 1) & m;
                    if (mm == 0)
                    {
                        list[First(m)].cell.get(i);
                        changed = true;
                        goto Clear2x;
                    }
                    if (((mm - 1) & mm) == 0)
                    {
                        a1 = First(m);
                        a2 = First(mm);
                        if ((a = tb[a1, a2]) >= 0)
                        {
                            m = (1LU << a) | (1LU << i);
                            changed |= list[a1].cell.mask(m);
                            changed |= list[a2].cell.mask(m);
                            m ^= MASK;
                            for (a = N2_1; a > a2; a--)
                                changed |= list[a].cell.mask(m);
                            while (--a > a1)
                                changed |= list[a].cell.mask(m);
                            while (--a >= 0)
                                changed |= list[a].cell.mask(m);
                            if (mk != mkb)
                                goto Clear2x;
                        }
                        else
                        {
                            tb[a1, a2] = i;
                            h1[hi] = a1;
                            h2[hi] = a2;
                            hi++;
                        }
                    }
                }
        Clear2x:
            while (--hi >= 0)
                tb[h1[hi], h2[hi]] = -1;
            if (changed)
                goto Loop;
            #endregion

            #region 3
            if (N > 4)
            {
                #region 3i
                hi = 0;
                int a3;
                for (e = head.right; e != head; e = e.right)
                {
                    m = e.mk;
                    a1 = First(m);
                    m = (m - 1) & m;
                    if (m == 0)
                        throw new Exception();
                    a2 = First(m);
                    if ((mm = (m - 1) & m) == 0)
                    {
                        i = e.eid;
                        for (a3 = N2_1; a3 > a2; a3--)
                            if (hit3(a1, a2, a3, i))
                                goto Clear3i;
                        while (--a2 > a1)
                            if (hit3(a1, a2, a3, i))
                                goto Clear3i;
                        while (--a1 >= 0)
                            if (hit3(a1, a2, a3, i))
                                goto Clear3i;
                        continue;
                    }
                    a3 = First(mm);
                    if (((mm - 1) & mm) == 0 && hit3(a1, a2, a3, e.eid))
                        goto Clear3i;
                }
            Clear3i:
                while (--hi >= 0)
                    tb3[h1[hi], h2[hi], h3[hi]] = 0;
                if (changed)
                    goto Loop;
                #endregion
                #region 3x
                hi = 0;
                for (i = 0; i < N2; i++)
                    if (ps[i] != 0)
                    {
                        m = ps[i];
                        a1 = First(m);
                        m = (m - 1) & m;
                        if (m == 0)
                        {
                            list[a1].cell.get(i);
                            changed = true;
                            goto Clear3x;
                        }
                        a2 = First(m);
                        if ((mm = (m - 1) & m) == 0)
                        {
                            for (a3 = N2_1; a3 > a2; a3--)
                                if (found3(a1, a2, a3, i))
                                    goto Clear3x;
                            while (--a2 > a1)
                                if (found3(a1, a2, a3, i))
                                    goto Clear3x;
                            while (--a1 >= 0)
                                if (found3(a1, a2, a3, i))
                                    goto Clear3x;
                            continue;
                        }
                        a3 = First(mm);
                        if (((mm - 1) & mm) == 0 && found3(a1, a2, a3, i))
                            goto Clear3x;
                    }
            Clear3x:
                while (--hi >= 0)
                    tb3[h1[hi], h2[hi], h3[hi]] = 0;
                if (changed)
                    goto Loop;
                #endregion
            }
            #endregion

            setsIQ.m[sid] = 0;
        }
        static int[] bs = new int[3];
        bool found3(int a1, int a2, int a3, int i)
        {
            int a;
            if ((a = tb3[a1, a2, a3]) > (1 << 8))
            {
                ulong m = (1LU << ((a & 0xff) - 1)) | (1LU << (((a >> 8) & 0xff) - 1)) | (1LU << i);
                changed |= list[a1].cell.mask(m);
                changed |= list[a2].cell.mask(m);
                changed |= list[a3].cell.mask(m);
                m ^= MASK;
                for (a = N2_1; a > a3; a--)
                    changed |= list[a].cell.mask(m);
                while (--a > a2)
                    changed |= list[a].cell.mask(m);
                while (--a > a1)
                    changed |= list[a].cell.mask(m);
                while (--a >= 0)
                    changed |= list[a].cell.mask(m);
                if (mk != mkb)
                    return true;
            }
            else
            {
                tb3[a1, a2, a3] = (a << 8) | (i + 1);
                if (a == 0)
                {
                    h1[hi] = a1;
                    h2[hi] = a2;
                    h3[hi] = a3;
                    hi++;
                }
            }
            return false;
        }
        bool hit3(int a1, int a2, int a3, int b)
        {
            Element e, ee;
            int a;
            if ((a = tb3[a1, a2, a3]) > (1 << 8))
            {
                bs[2] = b;
                bs[1] = (a & 0xff) - 1;
                bs[0] = ((a >> 8) & 0xff) - 1;
                ulong m = ~(list[b].mk | list[bs[1]].mk | list[bs[0]].mk);
                Array.Sort(bs, 0, 3);
                for (e = head.right, ee = list[bs[0]]; e != ee; e = e.right)
                {
                    changed |= e.cell.mask(m);
                    if (mk != mkb)
                        return true;
                }
                for (e = e.right, ee = list[bs[1]]; e != ee; e = e.right)
                {
                    changed |= e.cell.mask(m);
                    if (mk != mkb)
                        return true;
                }
                for (e = e.right, ee = list[bs[2]]; e != ee; e = e.right)
                {
                    changed |= e.cell.mask(m);
                    if (mk != mkb)
                        return true;
                }
                for (e = e.right; e != head; e = e.right)
                {
                    changed |= e.cell.mask(m);
                    if (mk != mkb)
                        return true;
                }
            }
            else
            {
                tb3[a1, a2, a3] = (a << 8) | (b + 1);
                if (a == 0)
                {
                    h1[hi] = a1;
                    h2[hi] = a2;
                    h3[hi] = a3;
                    hi++;
                }
            }
            return false;
        }
    }
    class IQ
    {
        public IQ(int n)
        {
            q = new int[n];
            m = new int[n];
            this.n = n;
        }
        public int e = 0, i = 0, n;
        public int[] m, q;
        public int Next()
        {
            if (e == i)
                return -1;
            int ret = q[e % n];
            m[ret] = 0;
            e++;
            return ret;
        }
        public void Add(int a)
        {
            if (m[a] != 0)
                return;
            m[a] = 1;
            q[i % n] = a;
            i++;

        }
    }
}